#include<bits/stdc++.h>
#include"game.h"
using namespace std;
const int N=5005;
mt19937 mt(time(0));
struct lb{
    int ne,la;
}b[N];
int be;
bool vis[N];
void era(int no){
    vis[no]=1;
    if(no==be)be=b[no].ne;
    b[b[no].ne].la=b[no].la;
    b[b[no].la].ne=b[no].ne;
}
vector<int> v,id;
void ed(int n){
    v.clear();
    int no=be;
    while(no!=n){
        v.push_back(id[no]);
        no=b[no].ne;
    }
    shuffle(v.begin(),v.end(),mt);
    while(no!=n){
        id[no]=v.back();
        v.pop_back();
        no=b[no].ne;
    }
}
vector<int> guess(int n,int limit){
    id.resize(n);
    memset(vis,0,sizeof(vis));
    be=0;
    for(int i=1;i<=n;++i){
        id[i-1]=i;
    }
    for(int i=0;i<n;++i){
        b[i].la=i-1;
        b[i].ne=i+1;
    }
    shuffle(id.begin(),id.end(),mt);
    int bas=count(id);
    for(int i=0;i<n;++i){
        if(vis[i])continue;
        vector<int> nd,dd;
        int no=be;
        while(no!=n){
            if(no==i){
                no=b[no].ne;
                continue;
            }
            swap(id[i],id[no]);
            int ct=count(id);
            if(ct==bas+2){
                era(i);era(no);
                bas+=2;
                break;
            }
            if(ct==bas-2){
                swap(id[i],id[no]);
                era(i);era(no);
                break;
            }
            if(ct==bas-1){
                swap(id[i],id[no]);
                dd.push_back(no);
                no=b[no].ne;
                continue;
            }
            if(ct==bas+1){
                swap(id[i],id[no]);
                nd.push_back(no);
                if(nd.size()==2)break;
                no=b[no].ne;
                continue;
            }
            swap(id[i],id[no]);
            no=b[no].ne;
        }
        if(nd.size()){
            for(int it:dd){
                era(it);
            }
            swap(id[i],id[nd[0]]);
            swap(id[i],id[nd[1]]);
            int ct=count(id);
            if(ct==bas+3){
                era(i);
                era(nd[0]);
                era(nd[1]);
                bas+=3;
                ed(n);
                continue;
            }
            if(ct==bas+2){
                era(i);
                era(nd[0]);
                bas+=2;
                ed(n);
                continue;
            }
            swap(id[i],id[nd[1]]);
            swap(id[i],id[nd[0]]);
            swap(id[i],id[nd[1]]);
            swap(id[i],id[nd[0]]);
            ct=count(id);
            if(ct==bas+3){
                era(i);
                era(nd[0]);
                era(nd[1]);
                bas+=3;
                ed(n);
                continue;
            }
            bas+=2;
            era(i);
            era(nd[1]);
            ed(n);
            continue;
        }
        ed(n);
    }
    return id;
}
